//核心思想就是归并，二路归并，先把两边排序好的复制出来，然后两边分别设指针比较，小的覆盖到原来数组去，然后指针向后
//然后运用递归解决问题
//时间复杂度是nlogn 空间复杂度是n
//一种改进方法是对于小于一定值的数组采用插入排序，而不是继续归并
//还有一种改进方法是对于已经排序好的两边，判断是否两边已经是正确的顺序了，如果是那么就不需要再进行归并
public class MergeSort extends InsertionSort_d{
    public void MySort(double data[])
    {
       double data_copy[]=new double[data.length];
       Sort(data,data_copy,0,data.length-1);     //传递过去的high是最后一个元素的位置
    }
    public void Sort(double data[],double data_copy[],int low,int high)
    {
        int mid=(low+high)/2;      //mid是中间的位置，在每次排序中是前一半数组的最后一个，所以要找后一半的第一个是mid+1
       if(high-low<=3)             //对于足够小的数组采用插入排序
       {
         super.MySort(data);
         return ;
       }
       Sort(data,data_copy,low,mid);
       Sort(data,data_copy,mid+1,high);
       if(data[mid]<data[mid+1])     //对于排好的两边判断是否已经是正确的顺序
       {
        return ;
       }
       Merge(data,data_copy,low,mid,high);                 //归并
    }
    public void Merge(double data[],double data_copy[],int low,int mid,int high)
    {
       for(int i=low;i<=high;i++)   //复制
       {
        data_copy[i]=data[i];
       }
       int a=low,b=mid+1;   //a和b分别指向两边未排好的元素
       for(int k=low;k<=high;k++)
       {
        if(a>mid)
        {
            data[k]=data_copy[b++];
        }
        else if(b>high)
        {
            data[k]=data_copy[a++];
        }
        else if(data_copy[a]>data_copy[b])
        {
            data[k]=data_copy[b++];
        }
        else
        {
            data[k]=data_copy[a++];   //相等的时候使用的也是左边的，这样可以保持稳定性
        }
       }
    }
}
//还有一种实现是自底向上的实现方式，那种方式使用循环
//那种方式先把所有单个元素当作已排序的，然后一点点增大步长，开始是两个两个元素进行归并，然后是四个四个（但是也是两组）